1. Field of the Invention
This invention relates to the calculation of a discrete Fourier transform of a periodically sampled signal. The invention may be utilized in many fields, such as in a frequency domain equalizer for information transmission channels.
2. Description of the Prior Art
Most prior art computations of a discrete Fourier transform require that all signal samples be available. In such systems, computations must be delayed until the signal of interest has been completely received. There is disclosed in the literature, however, a recursive computation of the discrete Fourier transform using the concepts of "moving window sampling" which need not wait until the end of data transmission prior to commencing the calculations. See, for example, George M. Dillard, "Recursivve Computation of the Discrete Fourier Transform with Applications to a Pulse-Doppler Radar System," Computers and Electrical Engineering, Vol. 1, pp 143-152, Pergamon, Oxford, 1973 and "Recursive Computation of the Discrete Fourier Transform with Applications to an FSK Communication Receiver", 1974 National Telemetering Conference Record, pp 263-265.
Situations occur in modern technological environments where it is desireable to perform recursive computations on various signals or functions. One such situation is in automatic equalization of transmission channels. When the equalization is carried out in the frequency domain, recursive computation of the discrete Fourier transform provides advantages, such as savings in time and minimization of hardware. Equalization of transmission channels in the prior art is generally conducted, however, in the time domain. The use of frequency domain equalization is not widespread, partly because of the common perception that the initialization of the equalization process must be delayed to allow for the reception of a complete characterization of the signal which is to be equalized. Moreover, prior attempts at applying recursive computations of the discrete Fourier transform to frequency domain equalizers have suffered from a tendency for errors to buildup, a problem common to recursive procedures. If errors occur in early computations, the use of the calculated coefficients in subsequent computations typically leads to amplification of the errors. Such error accumulation and amplification is likely to lead to intolerably erroneous results.